#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>

using namespace std;
using LL = long long;
const int N = 2e5 + 10;

int n;
LL dp[N][2];
char s[N];

void solve(){
    memset(dp, 0, sizeof dp);

    scanf("%d", &n);
    scanf("%s", s + 1);

    dp[1][(s[1] - '0')] = 1;


    for(int i = 2; i <= n; i ++){
        int x = s[i] - '0';
        int y = s[i - 1] - '0';

        dp[i][x] = 1;
        if(x == y){
            dp[i][x] += dp[i - 1][x ^ 1];
        }else{
            dp[i][x] += dp[i - 1][x ^ 1];
            int j = i - 2;
            while(j > 0 && dp[j][x ^ 1]){
                dp[i][x] += dp[j][x ^ 1];
                j--;
            }
        }
    }



    LL res = 0;
    for(int i = 1; i <= n; i ++){
        res = (LL) res + dp[i][0];
        res = (LL) res + dp[i][1];
    }

    printf("%lld\n", res);
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    int T;
    scanf("%d", &T);
    while(T--){
        solve();
    }

    return 0;
}